﻿using System;
using System.Text;

namespace Maman18
{
    #region SearchOptions

    public enum SearchOptions
    {
        /// <summary>
        /// Search for the exact key
        /// </summary>
        Exact,

        /// <summary>
        /// Search for small or equal key
        /// </summary>
        Smaller,

        /// <summary>
        /// Search for big or equal key
        /// </summary>
        Larger
    }

    #endregion

    /// <summary>
    /// Represents a Red-Black binary search tree
    /// </summary>
    public class RedBlackTree<TKey, TValue> where TKey : IComparable<TKey>
    {
        #region Node

        public enum NodeColor
        {
            Red,
            Black
        }

        public static readonly RedBlackNode NullNode = new RedBlackNode() { Color = NodeColor.Black };

        public class RedBlackNode
        {
            #region Properties

            public RedBlackNode Parent { get; set; }
            public RedBlackNode LeftChild { get; set; }
            public RedBlackNode RightChild { get; set; }

            public NodeColor Color { get; set; }

            public TKey Key { get; set; }
            public TValue Value { get; set; }

            public bool HasParent
            {
                get 
                { 
                    return (this.Parent != NullNode); 
                }
            }

            public bool HasLeftChild
            {
                get
                {
                    return (this.LeftChild != NullNode);
                }
            }

            public bool HasRightChild
            {
                get
                {
                    return (this.RightChild != NullNode);
                }
            }

            public bool IsLeaf
            {
                get
                {
                    return (!this.HasLeftChild && !this.HasRightChild);
                }
            }

            public bool IsLeftChild
            {
                get
                {
                    return (this.HasParent && (this.Parent.LeftChild == this));
                }
            }

            public bool IsRightChild
            {
                get
                {
                    return (this.HasParent && (this.Parent.RightChild == this));
                }
            }

            #endregion

            #region Ctors

            public RedBlackNode()
            {
                this.Parent = this.LeftChild = this.RightChild = NullNode;
            }

            #endregion

            #region Methods

            /// <summary>
            /// Gets this node successor
            /// </summary>
            /// <returns></returns>
            public RedBlackNode Successor()
            {
                RedBlackNode successor = NullNode;

                if (this.HasRightChild)
                {
                    // Successor is the minimum of the sub-right tree
                    successor = this.RightChild.GetMinimum();
                }
                else
                {
                    RedBlackNode currentNode = this;
                    successor = this.Parent;

                    while (currentNode.IsRightChild)
                    {
                        currentNode = successor;
                        successor = successor.Parent;
                    }
                }

                return (successor);
            }

            /// <summary>
            /// Swap this node with another one
            /// </summary>
            /// <param name="other"></param>
            /// <returns></returns>
            public void Swap(RedBlackNode other)
            {
                RedBlackNode tmpNode;

                // Swap parents
                if (this.IsLeftChild)
                {
                    this.Parent.LeftChild = other;
                }
                else if (this.IsRightChild)
                {
                    this.Parent.RightChild = other;
                }

                if (other.IsLeftChild)
                {
                    other.Parent.LeftChild = this;
                }
                else if (other.IsRightChild)
                {
                    other.Parent.RightChild = this;
                }

                tmpNode = other.Parent;
                other.Parent = this.Parent;
                this.Parent = tmpNode;

                // Swap left child
                if (this.HasLeftChild)
                {
                    this.LeftChild.Parent = other;
                }

                if (other.HasLeftChild)
	            {
		            other.LeftChild.Parent = this;
	            }

                tmpNode = other.LeftChild;
                other.LeftChild = this.LeftChild;
                this.LeftChild = tmpNode;

                // Swap right child
                if (this.HasRightChild)
                {
                    this.RightChild.Parent = other;
                }

                if (other.HasRightChild)
                {
                    other.RightChild.Parent = this;
                }

                tmpNode = other.RightChild;
                other.RightChild = this.RightChild;
                this.RightChild = tmpNode;
            }

            /// <summary>
            /// Gets this node tree level
            /// </summary>
            /// <returns></returns>
            public int GetNodeLevel()
            {
                if (!this.HasParent)
                {
                    return (0);
                }
                else
                {
                    return (this.Parent.GetNodeLevel() + 1);
                }
            }

            /// <summary>
            /// Gets the max level of this node dynasty
            /// </summary>
            /// <returns></returns>
            public int GetNodeHeight()
            {
                if (this.IsLeaf)
                {
                    return (this.GetNodeLevel());
                }
                else
                {
                    int leftDepth = 0;
                    if (this.HasLeftChild)
                    {
                        leftDepth = this.LeftChild.GetNodeHeight();
                    }

                    int rightDepth = 0;
                    if (this.HasRightChild)
                    {
                        leftDepth = this.RightChild.GetNodeHeight();
                    }

                    return (Math.Max(leftDepth, rightDepth));
                }
            }

            /// <summary>
            /// Gets this node minimum child
            /// </summary>
            /// <returns></returns>
            public RedBlackNode GetMinimum()
            {
                RedBlackNode current = this;
                
                while (current.HasLeftChild)
                {
                    current = current.LeftChild;
                }

                return (current);
            }

            #endregion
        }

        #endregion

        #region Properties

        public RedBlackNode Root { get; set; }

        /// <summary>
        /// Gets this tree size
        /// </summary>
        public int Size { get; private set; }
        
        /// <summary>
        /// Gets whether this tree is empty or not
        /// </summary>
        public bool IsEmpty
        {
            get
            {
                return (this.Root == NullNode);
            }
        }

        #endregion

        #region Ctors

        /// <summary>
        /// Create an empty RedBlackTree
        /// </summary>
        public RedBlackTree()
        {
            this.Root = NullNode;
            this.Size = 0;
        }

        #endregion

        #region Methods

        /// <summary>
        /// Rotates a node to the left
        /// </summary>
        /// <param name="node"></param>
        private void LeftRotate(RedBlackNode node)
        {
            // Get the node to replace after rotate
            RedBlackNode rotateNode = node.RightChild;

            // Move the left sub-tree of the rotate node to the original node
            node.RightChild = rotateNode.LeftChild;
            if (rotateNode.HasLeftChild)
                rotateNode.LeftChild.Parent = node;
            
            // Update the nodes parents
            rotateNode.Parent = node.Parent;
            if (!node.HasParent)
            {
                this.Root = rotateNode;
            }
            else if (node.IsLeftChild)
            {
                node.Parent.LeftChild = rotateNode;
            }
            else
            {
                node.Parent.RightChild = rotateNode;
            }

            // Move the node to the left
            rotateNode.LeftChild = node;
            node.Parent = rotateNode;
        }

        /// <summary>
        /// Rotates a node to the right
        /// </summary>
        /// <param name="node"></param>
        private void RightRotate(RedBlackNode node)
        {
            // Get the node to replace after rotate
            RedBlackNode rotateNode = node.LeftChild;

            // Move the right sub-tree of the rotate node to the original node
            node.LeftChild = rotateNode.RightChild;
            if (rotateNode.HasRightChild)
                rotateNode.RightChild.Parent = node;

            // Update the nodes parents
            rotateNode.Parent = node.Parent;
            if (!node.HasParent)
            {
                this.Root = rotateNode;
            }
            else if (node.IsLeftChild)
            {
                node.Parent.LeftChild = rotateNode;
            }
            else
            {
                node.Parent.RightChild = rotateNode;
            }

            // Move the node to the left
            rotateNode.RightChild = node;
            node.Parent = rotateNode;
        }

        /// <summary>
        /// Inserts a new item to the tree
        /// </summary>
        /// <param name="key"></param>
        /// <param name="value"></param>
        public void Insert(TKey key, TValue value)
        {
            // Creates the new node to insert with the color red
            RedBlackNode node = new RedBlackNode() { Key = key, Value = value, Color = NodeColor.Red };

            // Find the new node parent
            RedBlackNode parent = NullNode;
            RedBlackNode currentNode = this.Root;
            
            while (currentNode != NullNode)
            {
                parent = currentNode;

                // Compare keys to decide whether to continue left or right
                if (node.Key.CompareTo(currentNode.Key) < 0)
                    currentNode = currentNode.LeftChild;
                else
                    currentNode = currentNode.RightChild;
            }

            // Set the new node parent
            node.Parent = parent;

            // Check whether this is the first node
            if (parent == NullNode)
            {
                this.Root = node;
            }
            // Update the parent new child
            else if (node.Key.CompareTo(parent.Key) < 0)
            {
                parent.LeftChild = node;
            }
            else
            {
                parent.RightChild = node;
            }

            // Balance the tree
            this.InsertFixup(node);

            // Update the tree size
            this.Size++;
        }

        private void InsertFixup(RedBlackNode node)
        {
            while (node.Parent.Color == NodeColor.Red)
            {
                if (node.Parent.IsLeftChild)
                {
                    RedBlackNode uncle = node.Parent.Parent.RightChild;

                    if (uncle.Color == NodeColor.Red)
                    {
                        // Case 1
                        node.Parent.Color = NodeColor.Black;
                        uncle.Color = NodeColor.Black;
                        node.Parent.Parent.Color = NodeColor.Red;
                        node = node.Parent.Parent;
                    }
                    else
                    {
                        if (node.IsRightChild)
                        {
                            // Case 2
                            node = node.Parent;
                            this.LeftRotate(node);
                        }

                        node.Parent.Color = NodeColor.Black;
                        node.Parent.Parent.Color = NodeColor.Red;
                        this.RightRotate(node.Parent.Parent);
                    }
                }
                else if (node.Parent.IsRightChild)
                {
                    RedBlackNode uncle = node.Parent.Parent.LeftChild;

                    if (uncle.Color == NodeColor.Red)
                    {
                        // Case 1
                        node.Parent.Color = NodeColor.Black;
                        uncle.Color = NodeColor.Black;
                        node.Parent.Parent.Color = NodeColor.Red;
                        node = node.Parent.Parent;
                    }
                    else
                    {
                        if (node.IsLeftChild)
                        {
                            // Case 2
                            node = node.Parent;
                            this.RightRotate(node);
                        }

                        node.Parent.Color = NodeColor.Black;
                        node.Parent.Parent.Color = NodeColor.Red;
                        this.LeftRotate(node.Parent.Parent);
                    }
                }
            }

            this.Root.Color = NodeColor.Black;
        }

        /// <summary>
        /// Deletes a node from the tree
        /// </summary>
        /// <param name="node"></param>
        public void Delete(RedBlackNode node)
        {
            RedBlackNode replace = NullNode;

            if (!node.HasLeftChild  || !node.HasRightChild)
            {
                replace = node;
            }
            else
            {
                replace = node.Successor();
            }

            RedBlackNode replaceChild = NullNode;

            if (replace.HasLeftChild)
            {
                replaceChild = replace.LeftChild;
            }
            else
            {
                replaceChild = replace.RightChild;
            }

            replaceChild.Parent = replace.Parent;

            if (!replace.HasParent)
            {
                this.Root = replaceChild;
            }
            else if (replace.IsLeftChild)
            {
                replace.Parent.LeftChild = replaceChild;
            }
            else
            {
                replace.Parent.RightChild = replaceChild;
            }

            if (replace != node)
            {
                node.Swap(replace);
            }

            if (replace.Color == NodeColor.Black)
            {
                this.DeleteFixup(replaceChild);
            }

            // Update the tree size
            this.Size--;
        }

        private void DeleteFixup(RedBlackNode node)
        {
            while ((node != this.Root) && (node.Color == NodeColor.Black))
            {
                RedBlackNode uncle;

                if (node.IsLeftChild)
                {
                    uncle = node.Parent.RightChild;

                    // Case 1
                    if (uncle.Color == NodeColor.Red)
                    {
                        uncle.Color = NodeColor.Black;
                        node.Parent.Color = NodeColor.Red;
                        this.LeftRotate(node.Parent);
                        uncle = node.Parent.RightChild;
                    }

                    // Case 2
                    if ((uncle.LeftChild.Color == NodeColor.Black) && (uncle.RightChild.Color == NodeColor.Black))
                    {
                        uncle.Color = NodeColor.Red;
                        node = node.Parent;
                    }
                    // Case 3
                    else
                    {
                        if (uncle.RightChild.Color == NodeColor.Black)
                        {
                            uncle.LeftChild.Color = NodeColor.Black;
                            uncle.Color = NodeColor.Red;
                            this.RightRotate(uncle);
                            uncle = node.Parent.RightChild;
                        }

                        // Case 4
                        uncle.Color = node.Parent.Color;
                        node.Parent.Color = NodeColor.Black;
                        uncle.RightChild.Color = NodeColor.Black;
                        this.LeftRotate(node.Parent);
                        node = this.Root;
                    }
                }
                else if (node.IsRightChild)
                {
                    uncle = node.Parent.LeftChild;

                    // Case 1
                    if (uncle.Color == NodeColor.Red)
                    {
                        uncle.Color = NodeColor.Black;
                        node.Parent.Color = NodeColor.Red;
                        this.RightRotate(node.Parent);
                        uncle = node.Parent.LeftChild;
                    }

                    // Case 2
                    if ((uncle.LeftChild.Color == NodeColor.Black) && (uncle.RightChild.Color == NodeColor.Black))
                    {
                        uncle.Color = NodeColor.Red;
                        node = node.Parent;
                    }
                    // Case 3
                    else
                    {
                        if (uncle.LeftChild.Color == NodeColor.Black)
                        {
                            uncle.RightChild.Color = NodeColor.Black;
                            uncle.Color = NodeColor.Red;
                            this.LeftRotate(uncle);
                            uncle = node.Parent.LeftChild;
                        }

                        // Case 4
                        uncle.Color = node.Parent.Color;
                        node.Parent.Color = NodeColor.Black;
                        uncle.LeftChild.Color = NodeColor.Black;
                        this.RightRotate(node.Parent);
                        node = this.Root;
                    }
                }
            }

            node.Color = NodeColor.Black;
        }

        /// <summary>
        /// Search a key in this tree
        /// </summary>
        /// <param name="key"></param>
        /// <param name="options"></param>
        /// <returns></returns>
        public RedBlackNode SearchNode(TKey key, SearchOptions searchOption = SearchOptions.Exact)
        {
            RedBlackNode smaller = NullNode;
            RedBlackNode larger = NullNode;

            RedBlackNode current = this.Root;
            while ((current != NullNode) && (current.Key.CompareTo(key) != 0))
            {
                if (current.Key.CompareTo(key) < 0)
                {
                    smaller = current;
                    current = current.RightChild;
                }
                else
                {
                    larger = current;
                    current = current.LeftChild;
                }
            }

            if ((searchOption == SearchOptions.Exact) || 
                ((current != NullNode) && (current.Key.CompareTo(key) == 0)))
            {
                return (current);
            }
            else if (searchOption == SearchOptions.Smaller)
            {
                return (smaller);
            }
            else if (searchOption == SearchOptions.Larger)
            {
                return (larger);
            }

            return (NullNode);
        }

        /// <summary>
        /// Checks whether a key is exist in tree or not
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public bool IsExists(TKey key)
        {
            return (this.SearchNode(key) != NullNode);
        }

        /// <summary>
        /// Search a key in this tree
        /// </summary>
        /// <param name="key"></param>
        /// <returns></returns>
        public TValue Search(TKey key, SearchOptions searchOption = SearchOptions.Exact)
        {
            return (this.SearchNode(key, searchOption).Value);
        }

        /// <summary>
        /// Gets the current tree height
        /// </summary>
        public int GetTreeHeight()
        {
            return (this.Root.GetNodeHeight());
        }

        /// <summary>
        /// Returns a string represents the tree items by their sorted order
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder builder = new StringBuilder();

            RedBlackNode current = this.Root.GetMinimum();

            while (current != NullNode)
            {
                builder.Append(string.Format("{0} ", current.Value.ToString()));

                current = current.Successor();
            }

            return (builder.ToString());
        }

        #endregion
    }
}
